package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.*;

/**
 * @author zhangjy
 * @description 二叉树的层平均值
 * @date 2025/4/1 10:28
 */
public class AverageOfLevels_637 {

    public static void main(String[] args) {
        AverageOfLevels_637 averageOfLevels637 = new AverageOfLevels_637();

        TreeNode fifteen = new TreeNode(15);
        TreeNode seven = new TreeNode(7);
        TreeNode twenty = new TreeNode(20, fifteen, seven);
        TreeNode nine = new TreeNode(9);
        TreeNode root = new TreeNode(3, nine, twenty);

        List<Double> ans = averageOfLevels637.averageOfLevels2(root);
        ans.forEach(System.out::println);

    }

    /**
     * 官解-DFS；
     * 使用list，避免手动扩容。
     */
    List<Integer> countList = new ArrayList<>();
    List<Double> sumList = new ArrayList<>();

    public List<Double> averageOfLevels3(TreeNode root) {
        // 递归-记录每层节点总数和节点值之和
        averageRecursion3(root, 0);

        int length = countList.size();
        List<Double> ans = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            ans.add(i, sumList.get(i) / countList.get(i));
        }
        return ans;
    }

    public void averageRecursion3(TreeNode node, int index) {
        if (node == null) return;

        /**
         * 为什么官解判断是否首次访问本层节点，使用curIndex < sumList.size()，则非首次，而不是curIndex == sumList.size()，则为首次？
         * <p>
         * ——两者并无太大区别；
         * 虽然，ArrayList的扩容有几种情形，考虑到，可能不同情形下，扩容后的容量不一定为旧容量+1，所以采用curIndex < sumList.size()。
         * 但是，但是其size()获取的是当前集合实际存储的元素个数，而不是当前容量大小，所以使用size()方法即可
         *<p>
         * ArrayList的扩容机制；
         * 1.ArrayList容量为0：
         *      1）若无参构造，此时创建的ArrayList初始容量=0，添加第一个元素后，会把容量增加为10，后面进行正常扩容。
         *      2）若有参构造，且参数是容量=0，创建的ArrayList也是初始容量=0；但是，添加第一个元素后，容量=1，此时ArrayList已经装满，下次添加元素则进行正常扩容。
         *      2）若有参构造，且参数是空列表时，创建ArrayList后容量=0，添加第一个元素后，容量=1，此时ArrayList是满的，下次添加元素时需正常扩容。
         * 2.ArrayList容量>0，且它已经满了，则进行正常扩容；
         *      此时添加元素：每次扩容到原来的1.5倍（正常扩容）。
         */

        // 记录本层节点总数、节点值之和
        int curIndex = index;
        // 首次记录本层，则先扩容
        if (curIndex == sumList.size()) {
            countList.add(1);
            sumList.add((double) node.val);
        } else {
            countList.set(curIndex, countList.get(curIndex) + 1);
            sumList.set(curIndex, sumList.get(curIndex) + node.val);
        }
        curIndex++;

        // 向下递归
        averageRecursion3(node.left, curIndex);
        averageRecursion3(node.right, curIndex);
    }

    /**
     * DFS-参考官解；
     * 两个数组分别记录每层节点总数和节点值总和；
     * 使用数组，还要手动扩容（参考官解优化）
     */
    int[] counts = new int[]{};

    double[] sums = new double[]{};

    public List<Double> averageOfLevels2(TreeNode root) {
        // 记录每层节点总数和节点值之和
        averageRecursion(root, 0);

        int length = counts.length;
        List<Double> ans = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            ans.add(i, sums[i] / counts[i]);
        }
        return ans;
    }

    public void averageRecursion(TreeNode node, int index) {
        if (node == null) return;

        // 记录本层节点总数、节点值之和
        int curIndex = index;
        // 首次记录本层，手动扩容
        if (counts.length == curIndex) {
            counts = Arrays.copyOf(counts, counts.length + 1);
        }
        counts[curIndex] = counts[curIndex] + 1;

        if (sums.length == curIndex) {
            sums = Arrays.copyOf(sums, sums.length + 1);
        }
        sums[curIndex] = sums[curIndex] + node.val;
        curIndex++;

        // 向下递归
        averageRecursion(node.left, curIndex);
        averageRecursion(node.right, curIndex);
    }

    /**
     * 个解-BFS
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 一次遍历一层所有节点
        int curLayerSize = 0;
        double curLayerTotal;
        while (!queue.isEmpty()) {
            curLayerSize = queue.size();
            curLayerTotal = 0.0;
            for (int i = 0; i < curLayerSize; i++) {
                TreeNode poll = queue.poll();
                curLayerTotal += poll.val;

                // 非空入队左右节点
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
            // 计算每层平均值
            res.add(curLayerTotal / curLayerSize);
        }
        return res;
    }

}
